from typing import List


def dfs(digits, u, path, res, str_s):
    """
    :param digits: str
    :param u: int
    :param path: str
    :param res: list[str]
    :param str_s: list[str]
    :return: none
    """
    if u == len(digits):
        res.append(path)
    else:
        for i in str_s[ord(digits[u]) - ord('0')]:
            dfs(digits, u + 1, path + i, res, str_s)
    

def letterCombinations(digits: str) -> List[str]:
    if digits == "":
        return []
    res = []
    str_s = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
    dfs(digits, 0, "", res, str_s)
    return res


print(letterCombinations("23"))
